package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 1799. N 次操作后的最大分数和
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/22 9:06
 */
public class MaxScore {


    public static void main(String[] args) {
        MaxScore test = new MaxScore();

        // 1
//        int[] nums = {1, 2};

        // 11
//        int[] nums = {3, 4, 6, 8};

        // 14
        int[] nums = {1, 2, 3, 4, 5, 6};

        int i = test.maxScore(nums);
        System.out.println(i);
    }

    public int maxScore(int[] nums) {
        int length = nums.length;
        int n = 1 << length;
        int[] arr = new int[n];
        int[][] items = new int[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                items[i][j] = gcd(nums[i], nums[j]);
            }
        }
        int l = 20;
        int[] counts = new int[l];
        for (int i = 0; i < l; i++) {
            counts[i] = 1 << i;
        }
        for (int i = 3; i < n; i++) {
            int size = Integer.bitCount(i);
            if ((size & 1) == 1) {
                continue;
            }
            int s = size >> 1;
            for (int j = 0; j < l; j++) {
                if ((i & counts[j]) == 0) {
                    continue;
                }
                int t = i ^ counts[j];
                for (int k = j + 1; k < l; k++) {
                    if ((t & counts[k]) == 0) {
                        continue;
                    }
                    arr[i] = Math.max(arr[i], arr[t ^ counts[k]] + s * items[j][k]);
                }
            }
        }
        return arr[n - 1];
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}
